/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.dp;

/**
 * <p>
 * 子串的个数 输入两个字符串S和T，求出T在S的子序列个数。字符串的子序列为该串删除多个字符并保留字符相对顺序不变的子串。
 * 
 * (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
 * 
 * 输入: S = "rabbbit", T = "rabbit"
 * 输出： 3.
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月30日
 */
public class DistinctSubsequences {

    public int numDistinct(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        
        if(sLen==0 || tLen==0 || sLen<tLen){
            return 0;
        }
        //从开始到第j个t字符组成字符串在从S开始到第i个S字符组成字符串里的子序列个数
        int [][]dp = new int[sLen+1][tLen+1];//方便处理空串
        for(int i=0;i<=sLen;i++){
            dp[i][0] = 1;
        }
        for(int i=1;i<=sLen;i++){
            for(int j=1;j<=tLen;j++){
                if(s.charAt(i-1)==t.charAt(j-1)){
                    //加上dp[i-1][j-1]结果
                    dp[i][j] = dp[i-1][j]+dp[i-1][j-1];
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[sLen][tLen];
    }
    public static void main(String[] args) {
        DistinctSubsequences distinctSubsequences = new DistinctSubsequences();
        String s = "rabbbit";
        String t = "rabbit";
        System.out.println(distinctSubsequences.numDistinct(s, t));
        
        s = "Exampple";
        t = "Example";
        System.out.println(distinctSubsequences.numDistinct(s, t));
    }
}
